package com.ljx.offer;

import org.junit.Test;

import java.util.*;

/**
 * @author 李捷禧
 * Date: 2023/3/26
 * ClassName: C_38
 */

public class C_38 {
    List<String> list = new LinkedList<>();
    char[] c;
    /**
     * 回溯法
     * @param s
     * @return
     */
    public String[] permutation(String s) {
        c = s.toCharArray();
        dfs(0);
        return list.toArray(new String[list.size()]);
    }
    void dfs(int x){
        if(x == c.length - 1){
            list.add(String.valueOf(c));
            return;
        }
        HashSet<Character> set = new HashSet<>();
        for (int i = x; i < c.length; i++) {
            if(set.contains(c[i])) continue;
            set.add(c[i]);
            swap(i,x);
            dfs(x +1);
            swap(i,x);
        }
    }

    void swap(int i,int a){
        char t = c[i];
        c[i] = c[a];
        c[a] = t;
    }

    @Test
    public void test(){
        String[] strings = permutation("abc");
        for (String string : strings) {
            System.out.println(string);
        }
    }

}
